数学模型

Wang Haihua

🍈 🍉🍊 🍋 🍌


算法步骤

初始化

关于初始温度,初温越大,获得高质量解的机率越大,但花费较多的计算时间。温度越高对于劣解的接受能力越大(搜索范围越大),下降速度越慢(求解速度下降)。

关于初始解如何设定一般有以下方法:

(1)按照某一概率分布抽样一组$K$个解,以$K$个解的目标值的方差为初温(下面使用的时正态分布)。

(2)随机产生一组$K$个状态,确定两两状态间的最大目标差值,根据差值,利用一定的函数确定初温。

(3)利用经验公式。

产生新解

为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。

计算目标函数差

因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。

判断新解是否被接受

判断的依据是一个接受准则,最常用的接受准则是 Metropolis 准则

当新解被确定接受时,用新解代替当前解

当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。

温度更新,下一轮循环

伪代码

sa

一个关于使用模拟退火算法的视频